<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="en" xml:lang="en">
<head>
<title>problem01_18</title>
<!-- 2019-01-30 Wed 11:13 -->
<meta  http-equiv="Content-Type" content="text/html;charset=utf-8" />
<meta  name="generator" content="Org-mode" />
<meta  name="author" content="jacklisp" />
<style type="text/css">
 <!--/*--><![CDATA[/*><!--*/
  .title  { text-align: center; }
  .todo   { font-family: monospace; color: red; }
  .done   { color: green; }
  .tag    { background-color: #eee; font-family: monospace;
            padding: 2px; font-size: 80%; font-weight: normal; }
  .timestamp { color: #bebebe; }
  .timestamp-kwd { color: #5f9ea0; }
  .right  { margin-left: auto; margin-right: 0px;  text-align: right; }
  .left   { margin-left: 0px;  margin-right: auto; text-align: left; }
  .center { margin-left: auto; margin-right: auto; text-align: center; }
  .underline { text-decoration: underline; }
  #postamble p, #preamble p { font-size: 90%; margin: .2em; }
  p.verse { margin-left: 3%; }
  pre {
    border: 1px solid #ccc;
    box-shadow: 3px 3px 3px #eee;
    padding: 8pt;
    font-family: monospace;
    overflow: auto;
    margin: 1.2em;
  }
  pre.src {
    position: relative;
    overflow: visible;
    padding-top: 1.2em;
  }
  pre.src:before {
    display: none;
    position: absolute;
    background-color: white;
    top: -10px;
    right: 10px;
    padding: 3px;
    border: 1px solid black;
  }
  pre.src:hover:before { display: inline;}
  pre.src-sh:before    { content: 'sh'; }
  pre.src-bash:before  { content: 'sh'; }
  pre.src-emacs-lisp:before { content: 'Emacs Lisp'; }
  pre.src-R:before     { content: 'R'; }
  pre.src-perl:before  { content: 'Perl'; }
  pre.src-java:before  { content: 'Java'; }
  pre.src-sql:before   { content: 'SQL'; }

  table { border-collapse:collapse; }
  caption.t-above { caption-side: top; }
  caption.t-bottom { caption-side: bottom; }
  td, th { vertical-align:top;  }
  th.right  { text-align: center;  }
  th.left   { text-align: center;   }
  th.center { text-align: center; }
  td.right  { text-align: right;  }
  td.left   { text-align: left;   }
  td.center { text-align: center; }
  dt { font-weight: bold; }
  .footpara:nth-child(2) { display: inline; }
  .footpara { display: block; }
  .footdef  { margin-bottom: 1em; }
  .figure { padding: 1em; }
  .figure p { text-align: center; }
  .inlinetask {
    padding: 10px;
    border: 2px solid gray;
    margin: 10px;
    background: #ffffcc;
  }
  #org-div-home-and-up
   { text-align: right; font-size: 70%; white-space: nowrap; }
  textarea { overflow-x: auto; }
  .linenr { font-size: smaller }
  .code-highlighted { background-color: #ffff00; }
  .org-info-js_info-navigation { border-style: none; }
  #org-info-js_console-label
    { font-size: 10px; font-weight: bold; white-space: nowrap; }
  .org-info-js_search-highlight
    { background-color: #ffff00; color: #000000; font-weight: bold; }
  /*]]>*/-->
</style>
<link rel="stylesheet" type="text/css" href="css/markdownpad-github.css" />
<script type="text/javascript">
/*
@licstart  The following is the entire license notice for the
JavaScript code in this tag.

Copyright (C) 2012-2013 Free Software Foundation, Inc.

The JavaScript code in this tag is free software: you can
redistribute it and/or modify it under the terms of the GNU
General Public License (GNU GPL) as published by the Free Software
Foundation, either version 3 of the License, or (at your option)
any later version.  The code is distributed WITHOUT ANY WARRANTY;
without even the implied warranty of MERCHANTABILITY or FITNESS
FOR A PARTICULAR PURPOSE.  See the GNU GPL for more details.

As additional permission under GNU GPL version 3 section 7, you
may distribute non-source (e.g., minimized or compacted) forms of
that code without the copy of the GNU GPL normally required by
section 4, provided you include this license notice and a URL
through which recipients can access the Corresponding Source.


@licend  The above is the entire license notice
for the JavaScript code in this tag.
*/
<!--/*--><![CDATA[/*><!--*/
 function CodeHighlightOn(elem, id)
 {
   var target = document.getElementById(id);
   if(null != target) {
     elem.cacheClassElem = elem.className;
     elem.cacheClassTarget = target.className;
     target.className = "code-highlighted";
     elem.className   = "code-highlighted";
   }
 }
 function CodeHighlightOff(elem, id)
 {
   var target = document.getElementById(id);
   if(elem.cacheClassElem)
     elem.className = elem.cacheClassElem;
   if(elem.cacheClassTarget)
     target.className = elem.cacheClassTarget;
 }
/*]]>*///-->
</script>
</head>
<body>
<div id="content">
<h1 class="title">problem01_18</h1>
<div id="table-of-contents">
<h2>Table of Contents</h2>
<div id="text-table-of-contents">
<ul>
<li><a href="#sec-1">1. 递归训练(1)</a>
<ul>
<li><a href="#sec-1-1">1.1. 你的任务是使用递归调用,输出包含5个字符”abcde”的一个全排列,并计算这样的排列有多少种?(每个排列有5个字符,字符可以相同,比如[a a a a a]是一个排列,[a a a a b],是另外一个排列,并且[a a a b a] 与 [a b a a a] 是不同的排列.</a></li>
<li><a href="#sec-1-2">1.2. 使用递归调用,输出包含5个字符”abcde”的一个全排列,并计算这样的排列有多少种?(每个排列有5个字符,字符不能相同.)</a></li>
<li><a href="#sec-1-3">1.3. 你目前的任务,是使用递归的方法来往方格填写数字.从1~9这9个数字中填写到下图的方格(数字不能重复),并要求方格的所有行,所有列和对角元素的和都相等.</a></li>
<li><a href="#sec-1-4">1.4. 幻方填数</a></li>
<li><a href="#sec-1-5">1.5. 填数游戏(2016年蓝桥杯赛题)</a></li>
<li><a href="#sec-1-6">1.6. 填数游戏2</a></li>
</ul>
</li>
</ul>
</div>
</div>

<div id="outline-container-sec-1" class="outline-2">
<h2 id="sec-1"><span class="section-number-2">1</span> 递归训练(1)</h2>
<div class="outline-text-2" id="text-1">
</div><div id="outline-container-sec-1-1" class="outline-3">
<h3 id="sec-1-1"><span class="section-number-3">1.1</span> 你的任务是使用递归调用,输出包含5个字符”abcde”的一个全排列,并计算这样的排列有多少种?(每个排列有5个字符,字符可以相同,比如[a a a a a]是一个排列,[a a a a b],是另外一个排列,并且[a a a b a] 与 [a b a a a] 是不同的排列.</h3>
<div class="outline-text-3" id="text-1-1">
<p>
答案:<br  />
</p>
<div class="org-src-container">

<pre class="src src-c++"><span style="color: #A6E22E;">#include</span> <span style="color: #E6DB74;">&lt;stdio.h&gt;</span>
<span style="color: #A6E22E;">#include</span> <span style="color: #E6DB74;">&lt;iostream&gt;</span>
<span style="color: #66D9EF;">using</span> <span style="color: #66D9EF;">namespace</span> <span style="color: #AE81FF;">std</span>;
<span style="color: #66D9EF;">int</span> <span style="color: #F92672;">sum</span> = 0;<span style="color: #465457; font-style: italic;">//</span><span style="color: #465457; font-style: italic;">&#20840;&#23616;&#21464;&#37327;&#20889;&#22312;&#22806;&#37096;</span>
<span style="color: #66D9EF;">void</span> <span style="color: #F92672; font-style: italic;">dg</span>(<span style="color: #66D9EF;">int</span> <span style="color: #F92672;">temp</span>,<span style="color: #66D9EF;">char</span> <span style="color: #F92672;">p</span>[])
{
    <span style="color: #66D9EF;">if</span>(temp == 5)
    {
        <span style="color: #465457; font-style: italic;">//</span><span style="color: #465457; font-style: italic;">&#36882;&#24402;&#20986;&#21475;</span>
        <span style="color: #66D9EF;">for</span>(<span style="color: #66D9EF;">int</span> <span style="color: #F92672;">i</span> = 0;i &lt; 5;i++)
        {
            printf(<span style="color: #E6DB74;">"%c "</span>,p[i]);
        }
        printf(<span style="color: #E6DB74;">"\n"</span>);
        sum++;    <span style="color: #465457; font-style: italic;">//</span><span style="color: #465457; font-style: italic;">&#36825;&#26869;&#26641;&#21040;&#20102;&#21494;&#23376;&#33410;&#28857;,&#23558;&#25968;&#37327;&#21152;1</span>
        <span style="color: #66D9EF;">return</span>;
    }

    <span style="color: #465457; font-style: italic;">//</span>
    <span style="color: #66D9EF;">for</span>(<span style="color: #66D9EF;">char</span> <span style="color: #F92672;">i</span> = <span style="color: #E6DB74;">'a'</span>;i &lt;= <span style="color: #E6DB74;">'e'</span>;i++)
    {
            p[temp] = i;
            dg(temp+1,p);
    }
}
</pre>
</div>
</div>
</div>

<div id="outline-container-sec-1-2" class="outline-3">
<h3 id="sec-1-2"><span class="section-number-3">1.2</span> 使用递归调用,输出包含5个字符”abcde”的一个全排列,并计算这样的排列有多少种?(每个排列有5个字符,字符不能相同.)</h3>
<div class="outline-text-3" id="text-1-2">
<p>
答案:<br  />
</p>
<div class="org-src-container">

<pre class="src src-c++">   <span style="color: #465457; font-style: italic;">//</span><span style="color: #465457; font-style: italic;">&#21028;&#26029;&#23383;&#31526;c&#26159;&#21542;&#22312;&#23383;&#31526;&#25968;&#32452;&#20013;&#26377;&#37325;&#22797;</span>
<span style="color: #66D9EF;">int</span> <span style="color: #F92672; font-style: italic;">same</span>(<span style="color: #66D9EF;">int</span> <span style="color: #F92672;">len</span>,<span style="color: #66D9EF;">char</span> <span style="color: #F92672;">c</span>,<span style="color: #66D9EF;">char</span> <span style="color: #F92672;">p</span>[])
{
    <span style="color: #66D9EF;">for</span>(<span style="color: #66D9EF;">int</span> <span style="color: #F92672;">j</span> = 0;j &lt; len;j++)
    <span style="color: #66D9EF;">if</span>(p[j] == c)
        <span style="color: #66D9EF;">return</span> 1;

    <span style="color: #66D9EF;">return</span> 0;
}


<span style="color: #66D9EF;">void</span> <span style="color: #F92672; font-style: italic;">dg2</span>(<span style="color: #66D9EF;">int</span> <span style="color: #F92672;">temp</span>,<span style="color: #66D9EF;">char</span> <span style="color: #F92672;">p</span>[])
{
    <span style="color: #66D9EF;">if</span>(temp == 5)
    {
        <span style="color: #465457; font-style: italic;">//</span><span style="color: #465457; font-style: italic;">&#36882;&#24402;&#20986;&#21475;</span>
        <span style="color: #66D9EF;">for</span>(<span style="color: #66D9EF;">int</span> <span style="color: #F92672;">i</span> = 0;i &lt; 5;i++)
        {
            printf(<span style="color: #E6DB74;">"%c "</span>,p[i]);
        }
        printf(<span style="color: #E6DB74;">"\n"</span>);
        sum++;
        <span style="color: #66D9EF;">return</span>;
    }

    <span style="color: #66D9EF;">for</span>(<span style="color: #66D9EF;">char</span> <span style="color: #F92672;">i</span> = <span style="color: #E6DB74;">'a'</span>;i &lt;= <span style="color: #E6DB74;">'e'</span>;i++)
    {
        <span style="color: #465457; font-style: italic;">//</span><span style="color: #465457; font-style: italic;">&#36825;&#37324;&#38656;&#35201;&#21028;&#26029;,&#22914;&#26524;&#26032;&#21152;&#20837;&#30340;&#23383;&#31526;&#36319;&#21407;&#26377;&#30340;&#23383;&#31526;&#25968;&#32452;&#20013;&#30340;&#23383;&#31526;&#19981;&#21516;,&#23601;&#19981;&#33021;&#24448;&#19979;&#36208;&#20102;</span>
        <span style="color: #66D9EF;">if</span>(<span style="font-weight: bold;">!</span>same(temp,i,p))
        {
            p[temp] = i;
            dg2(temp+1,p);
        }

    }
}
</pre>
</div>
</div>
</div>

<div id="outline-container-sec-1-3" class="outline-3">
<h3 id="sec-1-3"><span class="section-number-3">1.3</span> 你目前的任务,是使用递归的方法来往方格填写数字.从1~9这9个数字中填写到下图的方格(数字不能重复),并要求方格的所有行,所有列和对角元素的和都相等.</h3>
<div class="outline-text-3" id="text-1-3">

<div class="figure">
<p><img src="img/task03.png" alt="task03.png" />
</p>
</div>
</div>
</div>

<div id="outline-container-sec-1-4" class="outline-3">
<h3 id="sec-1-4"><span class="section-number-3">1.4</span> 幻方填数</h3>
<div class="outline-text-3" id="text-1-4">
<p>
幻方是把一些数字填写在方阵中，使得行、列、两条对角线的数字之和都相等。
欧洲最著名的幻方是德国数学家、画家迪勒创作的版画《忧郁》中给出的一个4阶幻方。
他把1,2,3,&#x2026;16 这16个数字填写在4 x 4的方格中。
如下所示，即：
</p>


<pre class="example">
16 ?  ?  13
?  ?  11 ?
9  ?  ?  *
?  15 ?  1
</pre>

<p>
表中有些数字已经显露出来，还有些用?和*代替。
请你计算出? 和 * 所代表的数字。并把 * 所代表的数字作为本题答案提交。   
</p>

<pre class="example">
(提示:如果你能将上题完美解决,包括剪枝,那么这道题应该难不到你,需要注意的是,有一些方格已经填有数据了,需要跳过,并且需要适当的剪枝,否则全部遍历的话需要
遍历10!种填法,效率太低)
</pre>
</div>
</div>

<div id="outline-container-sec-1-5" class="outline-3">
<h3 id="sec-1-5"><span class="section-number-3">1.5</span> 填数游戏(2016年蓝桥杯赛题)</h3>
<div class="outline-text-3" id="text-1-5">
<p>
如下的10个格子,请填入0~9的数字。要求：连续的两个数字不能相邻。（左右、上下、对角都算相邻）
一共有多少种可能的填数方案？请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
</p>


<div class="figure">
<p><img src="img/task05.png" alt="task05.png" />
</p>
</div>
</div>
</div>

<div id="outline-container-sec-1-6" class="outline-3">
<h3 id="sec-1-6"><span class="section-number-3">1.6</span> 填数游戏2</h3>
<div class="outline-text-3" id="text-1-6">
<p>
如下图所示六角形中，填入1~12的数字。 使得每条直线上的数字之和都相同。
图中已经替你填好了3个数字，请你计算星号位置所代表的数字是多少？
</p>

<p>
你只需要提交一个整数即可.
</p>


<div class="figure">
<p><img src="img/task06.png" alt="task06.png" />
</p>
</div>
</div>
</div>
</div>
</div>
<div id="postamble" class="status">
<p class="author">Author: jacklisp</p>
<p class="date">Created: 2019-01-30 Wed 11:13</p>
<p class="creator"><a href="http://www.gnu.org/software/emacs/">Emacs</a> 25.3.1 (<a href="http://orgmode.org">Org</a> mode 8.2.10)</p>
<p class="validation"><a href="http://validator.w3.org/check?uri=referer">Validate</a></p>
</div>
</body>
</html>